package com.kizuki.algorithm.leetcode;

import java.util.*;

/**
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 *
 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
 */
public class 二叉树的后序遍历 {

    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root == null) {
                return list;
            }
            TreeNode pNode = root;
            LinkedList<TreeNode> stack = new LinkedList<>();
            while (pNode != null || !stack.isEmpty()) {
                if (pNode != null) {
                    stack.push(pNode);
                    list.add(pNode.val);
                    pNode = pNode.right;
                } else {
                    TreeNode node = stack.pop();
                    pNode = node.left;
                }
            }
            // 后序是左右根 可先遍历根右左再反转
            Collections.reverse(list);
            return list;
        }
    }

}
